package leetcode2;

import java.util.*;
class NumMatrix {
    int[][] arr=null;
    public NumMatrix(int[][] matrix) {
        arr=matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum=0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                sum+=arr[i][j];
            }
        }
        return sum;
    }
}
public class LeetCodeMain135 {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res=new ArrayList<>();
        Set<String> set=new HashSet<>();
        for (String string:strs) {
            char[] chars=string.toCharArray();
            Arrays.sort(chars);
            String str=new String(chars);
            set.add(str);
        }
        for (String s:set) {
            List<String> list=new ArrayList<>();
            for (String string:strs) {
                char[] chars=string.toCharArray();
                Arrays.sort(chars);
                String str=new String(chars);
                if (s.equals(str)){
                    list.add(string);
                }
            }
            res.add(list);
        }
        return res;
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new ArrayList<>();
        int n=s.length();
        int m=p.length();
        if (n<m){
            return list;
        }
        int[] cnt1=new int[26];
        int[] cnt2=new int[26];
        for (int i = 0; i < m; i++) {
            ++cnt1[s.charAt(i)-'a'];
            ++cnt2[p.charAt(i)-'a'];
        }
        for (int i = m; i < n; i++) {
            if (Arrays.equals(cnt1,cnt2)){
                list.add(i-m);
            }
            ++cnt1[s.charAt(i)-'a'];
            --cnt1[s.charAt(i-m)-'a'];
        }
        return list;
    }
    //字符串中的变位词
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }
        int n=s1.length();
        int m=s2.length();
        int[] cnt1=new int[26];
        int[] cnt2=new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(cnt1,cnt2)){
            return true;
        }
        for (int i = n; i < m; i++) {
            ++cnt2[s2.charAt(i)-'a'];
            --cnt2[s2.charAt(i-n)-'a'];
            if (Arrays.equals(cnt1,cnt2)){
                return true;
            }
        }
        return false;
    }
    //前缀和 和 map
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int counter=0;
        int maxLength=0;
        map.put(0,-1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==0){
                counter--;
            }else {
                counter++;
            }
            if (!map.containsKey(counter)){
                map.put(counter,i);
            }else {
                maxLength=Math.max(maxLength,i-map.get(counter));
            }
        }
        return maxLength;
    }
    //暴力超时
    public int findMaxLength1(int[] nums) {
        int length=0;
        for (int i = 0; i < nums.length; i++) {
            int zeroNum=nums[i]==0?1:0;
            int oneNum=nums[i]==1?1:0;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j]==0){
                    zeroNum++;
                }else {
                    oneNum++;
                }
                if (zeroNum==oneNum){
                   length=Math.max(zeroNum*2,length);
                }
            }
        }
        return length;
    }
}
